//
//  StockJobbing.swift
//  AlgorithmOne
//
//  Created by 刘彬彬 on 2020/3/9.
//  Copyright © 2020 LBB. All rights reserved.
//

import Foundation

class Stock {
    func maxProfit(_ prices: [Int]) -> Int {
        if (prices.count == 1) {
            return 0
        }
        //最大差值
        var maxDifference = 0
        for i in 0..<prices.count {
            if (isExistMoreBigValue(i, prices[i] + maxDifference, prices)) {
                maxDifference = maxValue(maxDifference,maxDifferenceValue(i, prices))
            }
        }
        return maxDifference
    }
    
    func maxDifferenceValue(_ index:Int,_ prices: [Int]) -> Int {
        var firstValue = prices[index];
        var maxDifference = 0;
        for i in index+1..<prices.count {
            if (firstValue > prices[i]) {
                firstValue = prices[i]
                break
            } else {
                let num = prices[i] - firstValue;
                maxDifference = maxValue(maxDifference, num)
            }
        }
        return maxDifference;
    }
    
    //数组中从index开始，有没有比vaule值(index位置的值+当前计算出来的最大差值)还大的数
    func isExistMoreBigValue(_ index:Int,_ value:Int,_ prices: [Int]) -> Bool {
        if (index == prices.count-1) {
            return false
        }
        for i in index..<prices.count {
            if (prices[i] > value) {
                return true
            }
        }
        return false
    }
    
    //两值取大
    func maxValue(_ a:Int,_ b:Int) -> Int {
        return a > b ? a : b
    }
    
    //暴力解 O(n*n)
    func violenceSolution(_ prices:[Int]) -> Int {
        var maxDifferenceValue = 0
        for i in 0..<prices.count-1 {
            for j in 0..<prices.count {
                let value = prices[j] - prices[i]
                if (value > maxDifferenceValue) {
                    maxDifferenceValue = value
                }
            }
        }
        return maxDifferenceValue
    }
    
    //最优解 O(n)
    func optimalSolution(_ prices:[Int]) -> Int {
        var minPrice = maxSizeToGrowTooSmall
        var maxDifferenceValue = 0
        for i in 0..<prices.count {
            if (prices[i] < minPrice) {
                minPrice = prices[i]
            } else {
                if (prices[i] - minPrice > maxDifferenceValue) {
                    maxDifferenceValue = prices[i] - minPrice
                }
            }
        }
        return maxDifferenceValue
    }
}
